package airthmetic.exercise.dp;

public class _123_买卖股票的最佳时机III {

    // 普通动态规划
    public static int maxProfit(int[] prices) {
        int n = prices.length;
        int[][][] dp = new int[n][3][2];

        for(int i=0; i<n; i++){
            if(i == 0){
                dp[i][1][0] = 0;
                dp[i][2][1] = -prices[i];
                dp[i][2][0] = 0;
                dp[i][1][1] = -prices[i];
                continue;
            }

            dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]);
            dp[i][1][1] = Math.max(dp[i-1][1][1], -prices[i]);

            dp[i][2][0] = Math.max(dp[i-1][2][0], dp[i-1][2][1] + prices[i]);
            dp[i][2][1] = Math.max(dp[i-1][2][1], dp[i-1][1][0] - prices[i]);

        }

        return dp[n-1][2][0];
    }


    // 状态压缩动态规划
    public static int maxProfit2(int[] prices) {
        int n = prices.length;
        int i_1_0 = 0;
        int i_1_1 = Integer.MIN_VALUE;
        int i_2_0 = 0;
        int i_2_1 = Integer.MIN_VALUE;

        for(int i=0; i<n; i++){
            i_2_0 = Math.max(i_2_0, i_2_1 + prices[i]);
            i_2_1 = Math.max(i_2_1, i_1_0 - prices[i]);
            i_1_0 = Math.max(i_1_0, i_1_1 + prices[i]);
            i_1_1 = Math.max(i_1_1, -prices[i]);
        }
        return i_2_0;
    }
}
